<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial073.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial070.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial075.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc145">10.4</A>&nbsp;&nbsp;Constraints</H2>

<A NAME="@default258"></A>
<A NAME="@default259"></A>
The constraints that <EM>ic_sets</EM> implements are the usual relations
over sets.
The membership (in/2, notin/2) and cardinality constraints
(#/2) establish
relationships between set variables and integer variables:

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<A HREF="../bips/lib/ic_sets/in-2.html"><B>?X in ?Set</B></A><A NAME="@default260"></A><DD CLASS="dd-description">
 The integer X is member of the integer set Set 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/notin-2.html"><B>?X notin ?Set</B></A><A NAME="@default261"></A><DD CLASS="dd-description">
 The integer X is not a member of the integer set Set 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/H-2.html"><B>#(?Set, ?Card)</B></A><A NAME="@default262"></A><DD CLASS="dd-description">
 Card is the cardinality of the integer set Set 
</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 10.2: Membership and Cardinality Constraints</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X ::[]..[1, 2, 3], 2 in X, 3 in X, #(X, 2).
X = [2, 3]
Yes (0.01s cpu)

?- X :: []..[1, 2, 3, 4], 3 in X, 4 notin X.
X = X{[3] \/ ([] .. [1, 2]) : _2161{1 .. 3}}
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
Possible constraints between two sets are equality, inclusion/subset
and disjointness:
<A NAME="@default263"></A>
<A NAME="@default264"></A>
<A NAME="@default265"></A>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X subset [1, 2, 3, 4].
X = X{([] .. [1, 2, 3, 4]) : _2139{0 .. 4}}
Yes (0.00s cpu)

?- X :: []..[1, 2, 3, 4], Y :: []..[3, 4, 5, 6], X subset Y.
X = X{([] .. [3, 4]) : _2176{0 .. 2}}
Y = Y{([] .. [3, 4, 5, 6]) : _2367{0 .. 4}}
There are 4 delayed goals.
Yes (0.00s cpu)

?- X :: [2] .. [1, 2, 3, 4], Y :: [3] .. [1, 2, 3, 4], X disjoint Y.
X = X{[2] \/ ([] .. [1, 4]) : _2118{1 .. 3}}
Y = Y{[3] \/ ([] .. [1, 4]) : _2213{1 .. 3}}
There are 2 delayed goals.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<A HREF="../bips/lib/ic_sets/sameset-2.html"><B>?Set1 sameset ?Set2</B></A><A NAME="@default266"></A><DD CLASS="dd-description">
 The sets Set1 and Set2 are equal 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/disjoint-2.html"><B>?Set1 disjoint ?Set2</B></A><A NAME="@default267"></A><DD CLASS="dd-description">
 The integer sets Set1 and Set2 are disjoint 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/includes-2.html"><B>?Set1 includes ?Set2</B></A><A NAME="@default268"></A><DD CLASS="dd-description">
 Set1 includes (is a superset) of the integer set Set2 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/subset-2.html"><B>?Set1 subset ?Set2</B></A><A NAME="@default269"></A><DD CLASS="dd-description">
 Set1 is a (non-strict) subset of the integer set Set2 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/intersection-3.html"><B>intersection(?Set1, ?Set2, ?Set3)</B></A><A NAME="@default270"></A><DD CLASS="dd-description">
 Set3 is the intersection of the integer sets Set1 and Set2 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/union-3.html"><B>union(?Set1, ?Set2, ?Set3)</B></A><A NAME="@default271"></A><DD CLASS="dd-description">
 Set3 is the union of the integer sets Set1 and Set2 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/difference-3.html"><B>difference(?Set1, ?Set2, ?Set3)</B></A><A NAME="@default272"></A><DD CLASS="dd-description">
 Set3 is the difference of the integer sets Set1 and Set2 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/symdiff-3.html"><B>symdiff(?Set1, ?Set2, ?Set3)</B></A><A NAME="@default273"></A><DD CLASS="dd-description">
 Set3 is the symmetric difference of the integer sets Set1 and Set2 
</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 10.3: Basic Set Relations</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Possible constraints between three sets are for example
intersection, union, difference and symmetric difference.
For example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: [2, 3] .. [1, 2, 3, 4],
   Y :: [3, 4] .. [3, 4, 5, 6],
   ic_sets : intersection(X, Y, Z).
X = X{[2, 3] \/ ([] .. [1, 4]) : _2127{2 .. 4}}
Y = Y{[3, 4] \/ ([] .. [5, 6]) : _2222{2 .. 4}}
Z = Z{[3] \/ ([] .. [4]) : _2302{[1, 2]}}
There are 6 delayed goals.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> Note that we needed to qualify the intersection/3 constraint with
the <EM>ic_sets</EM> module prefix because of a name conflict with a predicate from
the <EM>lists</EM> library of the same name.
</DL>
</TD>
</TR></TABLE>


<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> Note the lack of a complement constraint: this is because the complement
of a finite set is infinite and cannot be represented. Complements can be
modelled using an explicit universal set and a difference constraint.
</DL>
</TD>
</TR></TABLE>
<BR>
Finally, there are a number of n-ary constraints that apply to lists of sets:
disjointness, union and intersection. For example:

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<A HREF="../bips/lib/ic_sets/all_disjoint-1.html"><B>all_disjoint(+Sets)</B></A><A NAME="@default274"></A><DD CLASS="dd-description">
 Sets is a list of integers sets which are all disjoint 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/all_union-2.html"><B>all_union(+Sets, ?SetUnion)</B></A><A NAME="@default275"></A><DD CLASS="dd-description">
 SetUnion is the union of all the sets in the list Sets 
<DT CLASS="dt-description"><A HREF="../bips/lib/ic_sets/all_intersection-2.html"><B>all_intersection(+Sets, ?SetIntersection)</B></A><A NAME="@default276"></A><DD CLASS="dd-description">
 SetIntersection is the intersection of all the sets in the list Sets 
</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 10.4: N-ary Set Relations</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- intsets(Sets, 5, 1, 5), all_intersection(Sets, Common).
Sets = [_2079{([] .. [1, 2, 3, 4, 5]) : _2055{0 .. 5}}, ... ]
Common = Common{([] .. [1, 2, 3, 4, 5]) : _3083{0 .. 5}}
There are 24 delayed goals.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
In most positions where a set or set variable is expected one can also
use a set expression. A set expression is composed from ground sets
(integer lists), set variables, and the following set operators:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
Set1 /\ Set2       % intersection
Set1 \/ Set2       % union
Set1 \ Set2        % difference
</PRE></BLOCKQUOTE>
When such set expressions occur, they are translated into auxiliary
<A HREF="../bips/lib/ic_sets/intersection-3.html"><B>intersection/3</B></A><A NAME="@default277"></A>,
<A HREF="../bips/lib/ic_sets/union-3.html"><B>union/3</B></A><A NAME="@default278"></A> and
<A HREF="../bips/lib/ic_sets/difference-3.html"><B>difference/3</B></A><A NAME="@default279"></A>
constraints, respectively.<BR>
<BR>
<HR>
<A HREF="tutorial073.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial070.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial075.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
